package com.test.daily.leetcode.y2022.m06.day0630.home.v01;

/**
 * @author Tom on 2022/6/30
 */
public class Solution {

    public static void main(String[] args) {
        new Solution().numPrimeArrangements(100);
    }
    public int numPrimeArrangements(int n) {

        if(n == 1 || n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }
        int primeCount = 2;
        for(int i = 4; i <= n; i++){
            boolean isPrime = true;
            for(int j = 2; j <= Math.sqrt(i); j++){
                if(i % j == 0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime){
                primeCount++;
            }
        }
        long sum = 1;
        int noPrimeCount = n - primeCount;
        while (primeCount > 1){
            sum *= primeCount--;
            sum %= 1000000007;
        }
        while(noPrimeCount > 1){
            sum *= noPrimeCount--;
            sum %= 1000000007;
        }
        return (int)sum%1000000007;
    }
}
